// https://www.acwing.com/user/myspace/index/92692/
// 第一次见用模拟退火写算法题还过了的

#include <bits/stdc++.h>
#define N 15
#define int long long
using namespace std;
double T, start_T, del_T, low_T;
int INF;
int B[N], fa[N], n, Map[N + N][N + N], x, y, z, ans, m;
double rand_double() { return rand() / (double)RAND_MAX; }
void addedge(int x, int y, int z) {
  Map[x][y] = min(Map[x][y], z);
  Map[y][x] = min(Map[y][x], z);
}
void init() {
  srand(6662333);
  start_T = 23333;
  del_T = 0.99;
  low_T = 1e-9;
  INF = 12345678987654321;
  ans = INF;
  for (int i = 0; i <= 20; i++)
    for (int j = 0; j <= 20; j++) Map[i][j] = Map[j][i] = INF;
}
int find(int x) {
  if (x == B[x])
    return x;
  else
    return B[x] = find(B[x]);
}
void merge(int x, int y) {
  int fx = find(x);
  int fy = find(y);
  if (fx == fy) return;
  B[fx] = fy;
}
int dfs_sum(int v, int Fa, int dep) {
  int res = dep * Map[Fa][v];
  for (int i = 1; i <= n; i++) {
    if (fa[i] != v || Fa == i) continue;
    res += dfs_sum(i, v, dep + 1);
  }
  return res;
}
bool judge() {
  for (int i = 1; i <= n; i++) B[i] = i;

  for (int i = 1; i <= n; i++) {
    bool skip = false;
    if (find(i) == find(fa[i])) skip = true;
    if (i != fa[i] && skip) return false;
    merge(i, fa[i]);
  }
  return true;
}
int SA_main(int root) {  //退火主要部分
  int res = dfs_sum(root, 0, 0);
  //    if (root != 1ll) printf("res = %lld\n", res), system("pause");
  T = start_T;
  while (T > low_T) {
    int change, go;
    do {
      change = rand() % n + 1;
      go = rand() % n + 1;
    } while (change == go || change == root);
    int deposit = fa[change];
    fa[change] = go;
    if (!judge()) {
      fa[change] = deposit;
      continue;
    }
    int nxt = dfs_sum(root, 0, 0);
    double depos = exp((res - nxt) / T);
    if (nxt < res || depos > rand_double())
      res = nxt;
    else
      fa[change] = deposit;
    T *= del_T;
  }
  // cout << res << endl;
  return res;
}
void read() {
  scanf("%lld%lld", &n, &m);
  for (int i = 1; i <= m; i++) {
    scanf("%lld%lld%lld", &x, &y, &z);
    addedge(x, y, z);
  }
}
void solve() {
  if (n == 1) {
    ans = 0;
    return;
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) fa[j] = i;
    fa[i] = 0;
    for (int j = 1; j <= 16; j++) ans = min(ans, SA_main(i));
  }
}
void write() { cout << ans << endl; }

signed main() {
  init();
  read();
  solve();
  write();
  return 0;
}
